/* 求两个递增序列合并后的中位数 */

#include <iostream>
#include "sqlist.cpp"
using namespace std;

// 找两个递增序列合并后的中位数 -- 方法一
float Find(Sqlist &A, Sqlist &B)
{
  int i, j, k;
  i = j = k = 0;
  
  // 先将两个递增序列合并成一个递增序列C
  Sqlist C;
  while (i < A.length && j < B.length)
    if (A.data[i] < B.data[j])
      C.data[k++] = A.data[i++];
    else
      C.data[k++] = B.data[j++];
  
  while (i < A.length)
    C.data[k++] = A.data[i++];
  
  while (j < B.length)
    C.data[k++] = B.data[j++];
  
  // 求出C的中位数
  bool obb = C.length % 2 == 1; // 元素个数的奇偶性
  int mid_id = (A.length + B.length - 1) / 2; // 中间元素索引
  return obb ? C.data[mid_id] : (C.data[mid_id] + C.data[mid_id+1]) / 2.0;
  
} 


float find_k(Sqlist &A, Sqlist &B, int k)
{
  // 不妨令 A的查找范围 <= B的查找范围
  if (A.length > B.length)
  {
    return find_k(B, A, k);
  }
  
  // 查找范围
  int a0 = 0, b0 = 0;
  
  while (true)
  {
    // 如果A的查找范围为空
    if (A.length == a0) return B.data[b0 + k - 1];
    
    // 查找最小值，返回结果
    if (k == 1) return min(A.data[a0], B.data[b0]);
    
    int a_id = min(A.length, a0 + k / 2);
    int b_id = b0 + k - k / 2; // 防止int下溢
    
    // 更新查找范围
    if (A.data[a_id-1] < B.data[b_id-1])
    {
      k -= a_id - a0;
      a0 = a_id;
    }
    else
    {
      k -= b_id - b0;
      b0 = b_id;
    }
  }
}

// 找两个递增序列合并后的中位数 -- 方法二
float find(Sqlist &A, Sqlist &B)
{
  bool isEven = (A.length + B.length) % 2 ? false : true;
  
  int k = (A.length + B.length) / 2;
  
  if (isEven)
    return (find_k(A, B, k) + find_k(A, B, k+1)) / 2.0;
  else
    return find_k(A, B, k+1);
}

int main()
{
  // 创建两个递增有序表
  Sqlist A = {{11, 12, 13, 14, 15, 17, 19, 20}, 8};
  Sqlist B = {{2, 4, 6, 8, 20}, 5};
  
  // 找到两个表的中位数
  cout << find(A, B) << endl;
}
